from typing import List


class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if(len(matrix) == 0):
            return []
        res = []
        h = len(matrix)
        w = len(matrix[0])
        hl = 0
        wl = 0
        dx, dy = 1, 0
        x, y = -1, 0
        index = 0
        while(True):
            x, y = x+dx, y+dy
            if(hl == h or wl == w):
                break
            if(x == w):
                hl = hl + 1
                x = x - 1
                dx, dy = 0, 1
            elif(y == h):
                w = w - 1
                y = y - 1
                dx, dy = -1, 0
            elif(wl > x):
                h = h-1
                x = x+1
                dx, dy = 0, -1
            elif(hl > y):
                wl = wl+1
                y = y + 1
                dx, dy = 1, 0
            else:
                print(x, y)
                res.append(matrix[y][x])

        return res


if __name__ == "__main__":
    # [1,2,3,6,9,8,7,4,5]
    print(Solution().spiralOrder([[1, 2, 3], [4, 5, 6], [7, 8, 9]]))
# [1,2,3,4,8,12,11,10,9,5,6,7]
    print(Solution().spiralOrder(
        [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]))
    print(Solution().spiralOrder(
        [[1, 2, 3], [4, 5, 6], [7, 8, 9]]))
